/*
 * @lc app=leetcode.cn id=438 lang=cpp
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    unordered_map<char, int> ori, cnt;
    bool check()
    {
        for (auto &item : cnt)
        {
            if (ori[item.first] != item.second)
                return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ans;
        if (p.length() > s.length())
            return ans;

        for (const auto &c : p)
        {
            ori[c]++;
        }

        int r = 0;
        while (r < p.length())
        {
            cnt[s[r++]]++;
        }
        while (r < s.length())
        {
            if (check())
            {
                ans.push_back(r - p.length());
            }
            cnt[s[r]]++;
            cnt[s[r - p.length()]]--;
            r++;
        }
        if (check())
        {
            ans.push_back(r - p.length());
        }

        return ans;
    }
};
// @lc code=end
